package com.cuz.daileetcode;

/**
 * @author cuzz
 * @version 1.0
 * @description: 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 22:01 2021/9/27
 **/
public class Day10 {

    static class S1 {
        static class LenIndex {
            int len;
            int index;

            public LenIndex(int len, int index) {
                this.len = len;
                this.index = index;
            }
        }

        public static String longestPalindrome(String s) {
            int maxLen = Integer.MIN_VALUE;
            int start = 0;
            for (int index = 0; index < s.length(); index++) {
                LenIndex lenIndex1 = maxLenOf(s, index, index);
                LenIndex lenIndex2 = maxLenOf(s, index, index + 1);
                if (lenIndex1.len >= lenIndex2.len) {
                    if (lenIndex1.len > maxLen) {
                        maxLen = lenIndex1.len;
                        start = lenIndex1.index;
                    }
                } else {
                    if (lenIndex2.len > maxLen) {
                        maxLen = lenIndex2.len;
                        start = lenIndex2.index;
                    }
                }
            }
            return s.substring(start, start + maxLen);
        }

        public static void main(String[] args) {
            //
            System.out.println(longestPalindrome("1cabaabac"));
            maxLenOf("abab", 2, 2);
        }

        private static LenIndex maxLenOf(String s, int left, int right) {
            while (left >= 0 && right < s.length()) {
                if (s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                } else {
                    break;
                }
            }
            return new LenIndex(right - left - 1, left + 1);
        }
    }


    static class S2 {
        public static String longestPalindrome(String s) {
            if (s == null || s.length() < 2) {
                return s;
            }
            boolean[][] dp = new boolean[s.length()][s.length()];
            int maxLen = 1;
            int start = 0;

            //dp[i][j]表示字符串从i到j（包括i，包括j）是否是回文
            //如果s.charAt(i)!=s.charAt(j) 那么一定不回文（两端不等）
            //如果s.charAt(i)==s.charAt(j)
            //1.如果 i 和j 之间没有字符 or i j之间之存在一个字符 那么 dp[i][j]=T33
            //不存在字符 但是两端相等->回文，存在一个字符 两端相等->回文
            //2.如果i j存在不只一个字符 那么 取决于去掉两端的子串是否回文
            //即 dp[i][j]=dp[i+1][j-1],
            //注意到i<j  dp[i][j]依赖于dp[i+1][j-1]（在表格的左下方） 我们一列一列的填表
            //let us code
            for (int j = 1; j < s.length(); j++) {
                for (int i = 0; i < j; i++) {
                    if (s.charAt(i)==s.charAt(j)) {
                        //加入 aaaa  i=0 j=1 2 的时候都不需要参考
                        if (j-i<=2){
                            dp[i][j]=true;
                        }else {
                            dp[i][j]=dp[i+1][j-1];
                        }
                    }
                    int tempLen = j - i + 1;
                    if (dp[i][j]&& tempLen >maxLen){
                        maxLen=tempLen;
                        start=i;
                    }
                }
            }
            return s.substring(start,start+maxLen);
        }
    }
}
